/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/merge-k-sorted-lists
   @Language: C++
   @Datetime: 19-05-30 14:54
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// Method 1, Using Merge Two, Time 196ms
class Solution {
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode H(-1), *p;
		for(p=&H; l1 && l2; p=p->next){
			if(l1->val<l2->val){
				p->next=l1;
				l1=l1->next;
			}
			else{
				p->next=l2;
				l2=l2->next;
			}
		}
		p->next=l1?l1:l2;
		return H.next;
	}
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		ListNode H(-1);
		for(int i=0; i<lists.size(); ++i)
			H.next=mergeTwoLists(H.next,lists[i]);
		return H.next;
	}
};


// Method 2, Using Merge Two, Time 48ms
class Solution {
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode H(-1), *p;
		for(p=&H; l1 && l2; p=p->next){
			if(l1->val<l2->val){
				p->next=l1;
				l1=l1->next;
			}
			else{
				p->next=l2;
				l2=l2->next;
			}
		}
		p->next=l1?l1:l2;
		return H.next;
	}
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		if (lists.size() < 1) return NULL;
		for(int i=0, j=lists.size()-1; j; ++i){
			i = (i>=j ? 0:i);
			lists[i] = mergeTwoLists(lists[i],lists[j--]);
		}
		return lists[0];
	}
};


// Method 3, Using heap, Time 68ms
class Solution {
	struct heapcomp{
		bool operator()(const ListNode *a, const ListNode *b)const{
			return a->val>b->val;   // min heap
		}
	};
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<ListNode*,vector<ListNode*>,heapcomp> heap;
		for(const auto &p:lists)
			if(p) heap.push(p);
		ListNode H(-1);
		for(ListNode *p=&H; heap.size(); heap.pop()){
			p=p->next=heap.top();
			if(p->next) heap.push(p->next);
		}
		return H.next;
	}
};
